package array;

/**
 * Rotate an array of n elements to the right by k steps.
 * <p>
 * For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
 * <p>
 * Note:
 * Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
 * <p>
 * [show hint]
 * <p>
 * Hint:
 * Could you do it in-place with O(1) extra space?
 * Related problem: Reverse Words in a String II
 * <p>
 * Credits:
 * Special thanks to @Freezen for adding this problem and creating all test cases.
 * <p>
 * 189
 *
 * @author Koizumi Sinya
 * @date 2018/03/20. 12:34
 * @edithor
 * @date
 */
public class Day4 {
    public static void rotate(int[] numbers, int k) {
        k %= numbers.length;//如果k长度超过数组的长度
        reverse(numbers, 0, numbers.length - 1);//翻转整个数组
        reverse(numbers, 0, k - 1);//翻转前k个数
        reverse(numbers, k, numbers.length - 1);//翻转剩下的数

        //[1,2,3,4,5,6,7] → [7,6,5,4,3,2,1] → [5,6,7,4,1,2,3] → [5,6,7,1,2,3,4]
    }

    public static void reverse(int[] numbers, int start, int end) {
        while (start < end) {
            int temp = numbers[start];
            numbers[start] = numbers[end];
            numbers[end] = temp;
            start++;
            end--;
        }
    }

    public static void bestTest1(int[] nums, int k) {
        int temp, previous;
        for (int i = 0; i < k; i++) {
            System.out.println("外循环");
            previous = nums[nums.length - 1];
            printArray(nums);
            for (int j = 0; j < nums.length; j++) {
                temp = nums[j];
                nums[j] = previous;
                previous = temp;
                System.out.println("内循环");
                printArray(nums);
            }

        }
    }

    /**
     * 利用新创建一个临时数组来接收对应的元素，
     * 然后再把临时的数组覆盖在原有的数组上
     *
     * @param nums
     * @param k
     */
    public static void bestTest2(int[] nums, int k) {
        int[] a = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            a[(i + k) % nums.length] = nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = a[i];
        }
    }


    public static void printArray(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(" " + arr[i]);
        }
        System.out.println();
    }
}

